package 二叉树.二叉树的直径;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/4/21 14:12
 * @description:求二叉树直径等效于求左右路径经过节点数的最大值减一，也就是说该节点左右孩子的最大深度加一
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1,new TreeNode(2,new TreeNode(4),new TreeNode(5)),new TreeNode(3));
        System.out.println(diameterOfBinaryTree(root));
    }

    static int ans;
    public static int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
    public static int depth(TreeNode node) {
        if (node == null) {
            return 0; // 访问到空节点了，返回0
        }
        int L = depth(node.left); // 左儿子为根的子树的深度
        int R = depth(node.right); // 右儿子为根的子树的深度
        ans = Math.max(ans, L+R+1); // 计算以该节点为起点的路径经过节点数的最大值即L+R+1 并更新ans
        return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
    }

}
